package bintree.heap.leetcode;

import java.util.*;

/**
 * @author yuisama
 * @date 2022年12月01日 18:03
 * @description 前K个高频单词
 */
public class Num692_TopKFreq {
    public List<String> topKFrequent(String[] words, int k) {
        // 存储每个字符串出现的次数
        Map<String,Integer> wordsTable = new HashMap<>();
        // 取大用小
        Queue<String> queue = new PriorityQueue<>((o1,o2) ->
                wordsTable.get(o1).equals(wordsTable.get(o2)) ? o2.compareTo(o1) :
                wordsTable.get(o1) - wordsTable.get(o2));
        // 1.第一遍扫描，存储每个出现的字符串及其出现次数
        for (String s : words) {
            wordsTable.put(s, wordsTable.getOrDefault(s,0) + 1);
        }
        // 2.第二遍扫描，将出现频率最高的前k个单词入队
        for (Map.Entry<String,Integer> entry : wordsTable.entrySet()) {
            queue.offer(entry.getKey());
            if (queue.size() > k) {
                queue.poll();
            }
        }
        // 此时队列中存储了所有出现频率最高的前k个单词
        LinkedList<String> result = new LinkedList<>();
        while (!queue.isEmpty()) {
            result.addFirst(queue.poll());
        }
        return result;
    }
}
